using System;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0209. 长度最小的子数组")]
    public class No0209_MinSubArrayLen : AbsBaseTestItem
    {
        /*
        给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
        */

        public override void OnTest()
        {
            // 子数组 [4,3] 是该条件下的长度最小的连续子数组。
            Assert.TestExe(MinSubArrayLen, 7, new int[] { 2, 3, 1, 2, 4, 3 }, 2);

            Assert.TestExe(MinSubArrayLen2, 7, new int[] { 2, 3, 1, 2, 4, 3 }, 2);

            Assert.TestExe(MinSubArrayLen3, 7, new int[] { 2, 3, 1, 2, 4, 3 }, 2);
        }

        /// <summary>
        ///  方法一：暴力法
        /// </summary>
        public int MinSubArrayLen(int s, int[] nums)
        {
            int n = nums.Length;
            if (n == 0)
            {
                return 0;
            }

            int ans = int.MaxValue;
            for (int i = 0; i < n; ++i)
            {
                int sum = 0;
                for (int j = i; j < n; ++j)
                {
                    sum += nums[j];
                    if (sum >= s)
                    {
                        ans = Math.Min(ans, j - i + 1);
                        break;
                    }
                }
            }

            return ans == int.MaxValue ? 0 : ans;
        }

        /// <summary>
        /// 方法二：前缀和 + 二分查找
        /// </summary>
        public int MinSubArrayLen2(int s, int[] nums)
        {
            int LowerBound(int[] a, int l, int r, int target)
            {
                int mid = -1, originL = l, originR = r;
                while (l < r)
                {
                    mid = (l + r) >> 1;
                    if (a[mid] < target) l = mid + 1;
                    else r = mid;
                }

                return (a[l] >= target) ? l : -1;
            };

            int n = nums.Length;
            if (n == 0)
            {
                return 0;
            }

            int ans = int.MaxValue;
            int[] sums = new int[n + 1];
            // 为了方便计算，令 size = n + 1
            // sums[0] = 0 意味着前 0 个元素的前缀和为 0
            // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
            // 以此类推
            for (int i = 1; i <= n; ++i)
            {
                sums[i] = sums[i - 1] + nums[i - 1];
            }

            for (int i = 1; i <= n; ++i)
            {
                int target = s + sums[i - 1];
                int bound = LowerBound(sums, i, n, target);
                if (bound != -1)
                {
                    ans = Math.Min(ans, bound - i + 1);
                }
            }

            return ans == int.MaxValue ? 0 : ans;
        }

        /// <summary>
        ///  方法三：双指针
        /// </summary>
        public int MinSubArrayLen3(int s, int[] nums)
        {
            int n = nums.Length;
            int ans = int.MaxValue;
            int start = 0, end = 0;
            int sum = 0;
            while (end < n)
            {
                sum += nums[end];
                while (sum >= s)
                {
                    ans = Math.Min(ans, end - start + 1);
                    sum -= nums[start];
                    start++;
                }
                end++;
            }
            return ans == int.MaxValue ? 0 : ans;
        }
    }
}
